class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end()); //先排序
        vector<vector<int> > ans;
        int pre = 0;  //第一个数
        unsigned int beg = 0, end = nums.size() - 1;  // 第二、三个数的位置
        int judge = 0; // 上一个三元组的cur
        unsigned int i = 0;   //计数
        if(nums.size()<3)
            return ans;
        else
        {
            while(i < (nums.size()  - 2 )&& nums[i] <= 0)
            {
                if(i > 0 && nums[i]==nums[i - 1])
                {
                    ++i;
                    continue;
                }
                if(nums[i] > 0)
                    return ans;
                beg = i + 1;
                end = nums.size() - 1;
                pre = nums[i];
                for (; beg < nums.size(); ++beg) {
                    if (beg > i + 1 && nums[beg] == nums[beg - 1]) {
                    continue;
                }
                    while (beg < end && nums[beg] + nums[end] >-pre){
                    --end;
                }
                if (beg == end) {
                    break;
                }
                if (nums[beg] + nums[end] == -pre) {
                    ans.push_back({pre, nums[beg], nums[end]});
                }
            }
                ++i;
            }
            return ans;
        }
    }
};

